package A1_二叉树;

import java.util.Arrays;

public class LC_106从中序与后序遍历序列构造二叉树 {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val){
            this.val=val;
        }
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val=val;
            this.left=left;
            this.right=right;
        }
    }
    public  TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder==null || inorder==null)
            return null;
        if(postorder.length==0 || inorder.length==0)
            return null;
        int rootval=postorder[postorder.length-1];
        TreeNode root=new TreeNode(rootval);
        if(postorder.length==1)
            return root;
        int index=0;
        for(index=0;index<inorder.length;index++)
            if(inorder[index]==rootval)
                break;
        //切中序数组：左中序  右中序
        int[] leftin=cutTree(inorder,0,index);
        int[] rightin=cutTree(inorder,index+1,inorder.length);
        int len;
        if(leftin==null)
            len=0;
        else
            len=leftin.length;
        //切后序数组：左后序  右后序
        int[] leftpost=cutTree(postorder,0,len);
        int[] rightpost=cutTree(postorder,len,postorder.length-1);

        root.left=buildTree(leftin,leftpost);
        root.right=buildTree(rightin,rightpost);
        return root;
    }
    public  int[] cutTree(int[] order,int begin,int end){
        if(end<=begin)
            return null;
//        int len=end-begin;
        int[] cutorder= Arrays.copyOfRange(order,begin,end);
        return cutorder;
    }
}
